Galois Field (GF)256 arithmetic is used in various error correcting codes including Reed-Solomon codes. Reed-Solomon codes are useful in many commercial applications such as remote access modems, compact disks and high definition television. An efficient implementation of the GF 256 arithmetic that improves the performance or lowers the cost of an integrated circuit is beneficial. Moreover, with the ever increasing demand for high-speed communication systems, reducing the critical path of an error correcting decoder is critical.
In conventional systems, GF arithmetic is implemented using polynomial representations for the field elements. This makes GF addition simple but requires complex multiplication circuits which require many clock cycles per multiply. Furthermore, the decoder requires that logarithms in the Galois Field be performed. This requires a table look-up operation or a circuit which needs many clock cycles to complete.
Prior art implementations of GF arithmetic are given in U.S. Pat. Nos. 4,037,093, 4,251,875, 4,473,887, 4,852,098, 4,918,638, 4,975,867, 5,502,665 all of which are incorporated herein by reference.